"""
5. 最长回文子串
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个字符串 s，找到 s 中最长的 回文 子串。



示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"


提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成
"""


class Solution:
    def longestPalindrome(self, s: str) -> str:
        """
        中心扩散法
        :param s:
        :return:
        """
        res = ""
        #奇数情况
        for i in range(len(s)):
            l = i - 1
            r = i + 1
            while l>=0 and r<len(s) and s[l] == s[r]:
                l-=1
                r+=1
            if r - l -1 >len(res):
                res = s[l+1:r]
        # print(res)
        for i in range(len(s)-1):
            if s[i] != s[i+1]:
                continue
            l = i - 1
            r = i + 2
            while l>=0 and r<len(s) and s[l] == s[r]:
                l-=1
                r+=1
            if r - l -1 >len(res):
                res = s[l+1:r]
        return res
    # def longestPalindrome(self, s: str) -> str:
    #     """
    #     维护个set，如果当前存在则移除
    #     :param s:
    #     :return:
    #     """
    #     res = 0
    #     set1 = set()
    #     l = 0
    #     r = 0
    #     len1 = len(s)
    #     while r < len1:
    #         while s[r] in set1:
    #             set1.remove(s[l])
    #             l+=1
    #         set1.add(s[r])
    #         res = max(res,r - l)
    #         r+=1
    #     return res
if __name__ == '__main__':
    print(1<<2)
    s = Solution()
    print(s.longestPalindrome("babad"))
    print(s.longestPalindrome("cbbd"))